package org.algorithm.Backtracking.leetcode131;

import java.util.ArrayList;
import java.util.List;

public class Solution {

    /**
     *  字符串切割
     */

    List<List<String>> res = new ArrayList<>();
    List<String> item = new ArrayList<>();

    public List<List<String>> partition(String s) {

        backtracking(s,0);
        return res;
    }

    private void backtracking(String s, int index) {
            if (s.length()==index){
                res.add(new ArrayList<>(item));
                return;
            }

        for (int i = index; i <s.length(); i++) {
             if (isPartition(s,index,i)){
                 String partition = s.substring(index,i+1);
                 item.add(partition);
                 backtracking(s,i+1);
                 item.remove(item.size()-1);
             }
        }
    }

    private boolean isPartition(String s, int start, int end) {
        if (start == end) {
            return true;
        }

        while (start <= end) {
            if (s.charAt(start) != s.charAt(end)) {
                return false;
            }

            start++;
            end--;
        }

        return true;
    }
}
